﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using MentalAlchemy.Atomics;
using MentalAlchemy.Molecules;

namespace machinelearning.molecules
{
	public class Logic
	{
	}

	//public abstract class Fact
	//{
	//    public abstract new bool Equals(object obj);
	//    public abstract bool Relevant(Fact obj);
	//}

	/// <summary>
	/// Fact to solve TSP problem.
	/// </summary>
	[Serializable]
	public class TspRule
	{
		public List<string> Premises = new List<string>(); // list of cities.
		public float Conclusion; // path length.

		/// <summary>
		/// [molecule]
		/// 
		/// Creates TSP rule from its string representation.
		/// </summary>
		/// <param name="str"></param>
		/// <returns></returns>
		public static TspRule FromString (string str)
		{
			// find conclusion.
			var brOpen = str.IndexOf('(');
			var brClose = str.IndexOf(')');
			var conclStr = str.Substring(brOpen+1, brClose - brOpen - 1);	// conclusion string.

			var pathStr = str.Substring(0, brOpen);
			var cities = pathStr.Split('-');

			var res = new TspRule();
			res.Conclusion = float.Parse(conclStr);
			res.Premises = new List<string>(cities);

			return res;
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Creates new TSP rule by merging beginning of the [rule1] and ending of the [rule2].
		/// Doesn't modify neither rule1 nor rule2.
		/// </summary>
		/// <param name="rule1"></param>
		/// <param name="rule2"></param>
		/// <returns></returns>
		public static TspRule Merge(TspRule rule1, TspRule rule2)
		{
			var res = new TspRule();
			res.Premises.AddRange(rule1.Premises);
			res.Premises.AddRange(rule2.Premises.GetRange(1, rule2.Premises.Count - 1));
			res.Conclusion = rule1.Conclusion + rule2.Conclusion;
			return res;
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Defines whether two rules have the same starting and finishing nodes.
		/// </summary>
		/// <param name="rule1"></param>
		/// <param name="rule2"></param>
		/// <returns></returns>
		public static bool HaveEqualPremises(TspRule rule1, TspRule rule2)
		{
			return rule1.Premises[0] == rule2.Premises[0] &&
			       rule1.Premises[rule1.Premises.Count - 1] == rule2.Premises[rule2.Premises.Count - 1];
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Finds out whether given rule contains prescribed string as one of its premises
		/// </summary>
		/// <param name="rule"></param>
		/// <param name="prem"></param>
		/// <returns></returns>
		public static bool ContainsPremise(TspRule rule, string prem)
		{
			return Strings.Contains(rule.Premises.ToArray(), prem, false);
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Defines whether rule2 can be applied after rule1.
		/// </summary>
		/// <param name="rule1"></param>
		/// <param name="rule2"></param>
		/// <returns></returns>
		public static bool Relevant(TspRule rule1, TspRule rule2)
		{
			return rule1.Premises[rule1.Premises.Count - 1] == rule2.Premises[0];
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Conversion to the string representation.
		/// </summary>
		/// <returns></returns>
		public override string ToString()
		{
			var res = Strings.Concat(Premises.ToArray(), "-");
			res += "(" + Conclusion + ")";
			return res;
		}
	}

	[Serializable]
	public class TspKnowledgeBase
	{
		public List<TspRule> Rules = new List<TspRule>();

		/// <summary>
		/// [molecule]
		/// 
		/// Finds out whether KB contains the rule with equal premises.
		/// </summary>
		/// <param name="rule"></param>
		/// <returns></returns>
		public bool HasRule (TspRule rule)
		{
			return HasRule(Rules, rule);
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Finds out whether given set of rules contains the rule with equal premises.
		/// </summary>
		/// <param name="rule"></param>
		/// <param name="rules"></param>
		/// <returns></returns>
		public static bool HasRule(List<TspRule> rules, TspRule rule)
		{
			foreach (var rule1 in rules)
			{
				if (TspRule.HaveEqualPremises(rule1, rule)) { return true; }
			}
			return false;
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Returns rule from a given set of rules which has equal premises with a specified rule.
		/// </summary>
		/// <param name="rule"></param>
		/// <param name="rules"></param>
		/// <returns></returns>
		public static TspRule GetRule(List<TspRule> rules, TspRule rule)
		{
			foreach (var rule1 in rules)
			{
				if (TspRule.HaveEqualPremises(rule1, rule)) { return rule1; }
			}
			return new TspRule();
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Returns rules from a given set of rules which has equal premises with a specified rule.
		/// </summary>
		/// <param name="rule"></param>
		/// <param name="rules"></param>
		/// <returns></returns>
		public static List<TspRule> GetRules(List<TspRule> rules, TspRule rule)
		{
			var res = new List<TspRule> ();
			foreach (var rule1 in rules)
			{
				if (TspRule.HaveEqualPremises(rule1, rule))
				{
					res.Add(rule1);
				}
			}
			return res;
		}


		/// <summary>
		/// [molecule]
		/// 
		/// Returns path (rule) with the shortest distance (smallest conclusion).
		/// </summary>
		/// <param name="rules"></param>
		/// <returns></returns>
		public static TspRule GetBestRule(List<TspRule> rules)
		{
			// select the best rule from the [rules] array.
			var solIdx = 0;
			for (int i = 1; i < rules.Count; i++)
			{
				if (rules[i].Conclusion < rules[solIdx].Conclusion)
				{
					solIdx = i;
				}
			}
			return rules[solIdx];
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Returns all rules, which can be applied after the given one.
		/// </summary>
		/// <param name="rule"></param>
		/// <returns></returns>
		public List<TspRule> GetRelevantRules(TspRule rule)
		{
			var res = new List<TspRule>();
			foreach (var r in Rules)
			{
				if (TspRule.Relevant(rule, r))
				{
					res.Add(r);
				}
			}
			return res;
		}

		#region - Save/Load operations. -
		public void Save(string file)
		{
			FileIO.Serialize(file, this);
		}

		public void Load(string file)
		{
			IFormatter formatter = new BinaryFormatter();
			Stream stream = new FileStream(file, FileMode.Open, FileAccess.Read, FileShare.None);
			if (stream.Length == 0) return;

			var kb = (TspKnowledgeBase)formatter.Deserialize(stream);
			stream.Close();

			Rules = new List<TspRule>(kb.Rules);
		} 

		// todo: import from a text file with simple format: city1-city2-city3-...-cityN(sum distance)
		/// <summary>
		/// [molecule]
		/// 
		/// Creates text representation of the KB. 
		/// </summary>
		/// <param name="filename"></param>
		public void Export2Text (string filename)
		{
			var lines = new List<string>();
			foreach (var rule in Rules)
			{
				lines.Add(rule.ToString());
			}
			File.WriteAllLines(filename, lines.ToArray(), Encoding.Default);
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Imports KB contents from a given text-file.
		/// </summary>
		/// <param name="filename"></param>
		public void ImportFromText (string filename)
		{
			Rules = new List<TspRule>();

			var lines = File.ReadAllLines(filename, Encoding.Default);
			foreach (var line in lines)
			{
				Rules.Add(TspRule.FromString(line));
			}
		}
		#endregion
	}

	/// <summary>
	/// [molecule]
	/// 
	/// Represents direct inference algorithm.
	/// </summary>
	public class TspDirectInference
	{
		public TspKnowledgeBase KnowledgeBase = new TspKnowledgeBase();
		public List<TspRule> AlgState = new List<TspRule>();

		/// <summary>
		/// [molecule]
		/// 
		/// Loads KB from the specified file and resets algorithm's state.
		/// </summary>
		/// <param name="filename"></param>
		public void Init (string filename)
		{
			KnowledgeBase.Load(filename);
			AlgState = new List<TspRule>();
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Loads KB from the specified graph and resets algorithm's state.
		/// </summary>
		/// <param name="graph"></param>
		public void Init(Graph graph)
		{
			foreach (var edge in graph.Edges)
			{
				var tempRule = new TspRule();
				tempRule.Premises = new List<string>();
				tempRule.Premises.Add(edge.BeginIdx.ToString());
				tempRule.Premises.Add(edge.EndIdx.ToString());
				tempRule.Conclusion = edge.Weight;

				if (!KnowledgeBase.HasRule(tempRule))
				{
					KnowledgeBase.Rules.Add(tempRule);
				}
			}
			AlgState = new List<TspRule>();
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Runs the direct inference algorithm for the prescribed start and finish cities.
		/// </summary>
		/// <param name="startCity">Beginning of the route.</param>
		/// <param name="finishCity">End of the route.</param>
		/// <param name="maxDist">Maximal allowed distance.</param>
		/// <returns></returns>
		public TspRule Run (string startCity, string finishCity, float maxDist)
		{
			// create prototype for a target rule.
			var targetRuleProt = new TspRule();
			targetRuleProt.Premises.Add(startCity);
			targetRuleProt.Premises.Add(finishCity);
			targetRuleProt.Conclusion = maxDist;

			// look for relevant rules for the target rule in current KB.
			var sols = TspKnowledgeBase.GetRules(KnowledgeBase.Rules, targetRuleProt);
			if (sols.Count > 0) { return TspKnowledgeBase.GetBestRule(sols); }

			// Init alg. state with the known information.
			AlgState.Add(new TspRule());
			AlgState[0].Premises.Add(startCity);	// init alg. state.
			AlgState[0].Conclusion = 0;

			// dictionary for distances.
			var distDict = new Dictionary<string, float>();
			foreach (var rule in KnowledgeBase.Rules)
			{
				foreach (var premise in rule.Premises)
				{
					if (!distDict.ContainsKey(premise))
					{
						distDict.Add(premise, maxDist);
					}
				}
			}

			// main cycle.
			while (true)
			{	// main algorithm cycle.
				var temp = TspKnowledgeBase.GetRule(AlgState, targetRuleProt);
				if (temp.Premises != null && temp.Premises.Count != 0) { return temp; }	// the solution is found.

				var newState = new List<TspRule>();
				foreach (var rule in AlgState)
				{
					// find rules which can be applied after [rule]
					var relRules = KnowledgeBase.GetRelevantRules(rule);

					foreach (var relRule in relRules)
					{
						var relEnd = relRule.Premises[relRule.Premises.Count - 1];
						if (!TspRule.ContainsPremise(rule, relEnd))	// if we didn't use the vertex [relEnd] in path [rule] before.
						{
							var newRule = TspRule.Merge(rule, relRule);

							// if the rule is already in the state (dublicate rule emerges).
							if (TspKnowledgeBase.HasRule(AlgState, newRule)) { continue; }

							if (newRule.Conclusion < maxDist && newRule.Conclusion < distDict[relEnd])
							{	// if the rule is feasible.
								newState.Add(newRule);
								distDict[relEnd] = newRule.Conclusion;

								if (!KnowledgeBase.HasRule(newRule))
								{
									KnowledgeBase.Rules.Add(newRule);
								}
							}

							if (relEnd == finishCity)
							{	// we found a possible solution.
								if (!TspKnowledgeBase.HasRule(sols, newRule)) sols.Add(newRule);
							}
						}
					}	// foreach (var relRule in relRules)
				}	// foreach (var rule in AlgState).

				if (newState.Count == 0)
				{	// we are stuck.
					if (sols.Count == 0)
					{
						// create and remember false rule.
						targetRuleProt.Conclusion = -1;
						KnowledgeBase.Rules.Add(targetRuleProt);
						return targetRuleProt;
					}
					break;
				}

				// otherwise update the state.
				AlgState = newState;
			}	// while (true).

			// select the best rule from the [sols] array.
			return TspKnowledgeBase.GetBestRule(sols);
		}

		/// <summary>
		/// [molecule]
		/// 
		/// Calculate distances matrix for all pairs of cities.
		/// </summary>
		/// <param name="graph"></param>
		/// <returns></returns>
		public float[,] CalculateDistanceMatrix (Graph graph)
		{
			var size = graph.AdjacencyMatrix.GetLength(0);
			var res = new float[size, size];

			// todo: convert graph into KB.
			Init(graph);

			const float MAX_DIST = 10000f;
			for (int i = 0; i < size; ++i)
			{
				res[i, i] = 0;
				for (int j = i + 1; j < size; j++)
				{
					var path = Run(i.ToString(), j.ToString(), MAX_DIST);
					res[i, j] = res[j, i] = path.Conclusion;
				}
			}

			return res;
		}
	}
}
